

def insertion_sort(array):
    """
    从数组第二个元素开始，与前面的比较大小，完成局部排序，然后从第三个元素开始，依次迭代
    :param array:
    :return:
    """
    for k in range(1, len(array)):
        cur = array[k]
        j = k
        while j > 0 and array[j-1] > cur:
            array[j] = array[j-1]
            j -= 1
        array[j] = cur